package com.example.teesystem.common.utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import static cn.hutool.core.util.NumberUtil.min;
import static java.lang.Math.max;

public class Test {

    static int count = 0;

    public static void exchange(char a, char b, char c, int n){
        if(n<0){
            return;
        }
        if(n == 2){
            System.out.println(a+"->"+b);
            System.out.println(a+"->"+c);
            System.out.println(b+"->"+c);
            count = count + 3;
        }
        else if(n == 1){
            System.out.println(a+"->"+c);
            count = count + 1;
        }
        exchange(a,c,b,n-1);
        System.out.println(a+"->"+c);
        exchange(b,a,c,n-1);
    }

    public static void exchange(char a, char b, char c, char d, int n){
        if(n<0){
            return;
        }
        if(n == 3){
            System.out.println(a+"->"+b);
            System.out.println(a+"->"+c);
            System.out.println(a+"->"+d);
            System.out.println(c+"->"+d);
            System.out.println(b+"->"+d);
            count = count+5;
        }
        else if(n == 2){
            System.out.println(a+"->"+b);
            System.out.println(a+"->"+d);
            System.out.println(b+"->"+d);
            count = count+3;
        }
        else if(n == 1){
            System.out.println(a+"->"+d);
            count = count+1;
        }
        exchange(a,b,d,c,n-3);
        exchange(a,b,d,n-(n-3));
        exchange(c,a,b,d,n-3);
    }

    public static int M4_mem(int n){
        int tmp,m = 1<<16;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        map.put(0,1);
        for(int i = 1; i < n; i++){
            for(int j = 1; j < i + 1; j++){
                tmp = 2*map.get(i-j)+(i<<j)-1;
                if(tmp<m) {
                    m = tmp;
                }
            }
            map.put(i,m);
            m = 1<<16;
        }
        return map.get(n-1);
    }

    public static int M4(int n){
        int tmp,m = 1<<16;
        if(1==n){
            return 1;
        }
        for(int i = 1; i < n; i++){
            tmp = 2*M4(n-i)+(1<<i)-1;
            if(tmp<m){
                m = tmp;
            }
        }
        return m;
    }

    public static Map<Integer,List<Integer>> map = new HashMap<>();

    public static void main(String[] args) {
        exchange('a','b','c','d',10);
        System.out.println(count);
        System.out.println(M4_mem(10));
        System.out.println(M4(10));
    }
}
